#include<bits/stdc++.h>
using namespace std;
#define pct __builtin_popcount
const int N=(1<<20)+100,M=1e9+7;
using ll=long long;
using ul=unsigned long long;
using vt=vector<int>;
int T,n,m,K,a[N],b[N],d[305][305],ans;
int f[(1<<18)+9][19][19],g[(1<<18)+9];
void ckmn(int &x,int y){if(x>y)x=y;}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    freopen("journey.in","r",stdin);
    freopen("journey.ans","w",stdout);
    int i,j,k,l,r,x,y,z;
    cin>>n>>m>>T;
    for(x=1;x<=n;++x)
        for(y=1;y<=n;++y)
            d[x][y]=M;
    while(m--){
        cin>>x>>y>>k;
        d[x][y]=min(d[x][y],k);
    }
    for(k=1;k<=n;++k)
        for(i=1;i<=n;++i)
            for(j=1;j<=n;++j)
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
    while(T--){
        cin>>K,ans=K*n;
        for(i=0;i<=(1<<n);++i)
            for(j=1,g[i]=M;j<=n;++j)
                for(k=1;k<=n;++k)
                    f[i][j][k]=M;
        g[0]=0;
        for(x=1;x<=n;++x)
            for(y=1;y<=n;++y)
                f[(1<<x-1)|(1<<y-1)][x][y]=d[x][y];
        for(k=1;k<(1<<n);++k){
            for(x=1;x<=n;++x)
                if((k>>x-1)&1)
                    for(y=1;y<=n;++y)
                        if((k>>y-1)&1){
                            for(z=1;z<=n;++z)
                                if(!((k>>z-1)&1))
                                    ckmn(f[k|(1<<z-1)][x][z],f[k][x][y]+d[y][z]);
                            ckmn(g[k],f[k][x][y]+(x==y?0:min(d[y][x],K)));
                        }
            ans=min(ans,g[k]+(n-pct(k))*K);
            for(x=1;x<=n;++x)
                for(y=1;y<=n;++y)
                    ckmn(f[k|(1<<x-1)|(1<<y-1)][x][y],g[k]+d[x][y]);
        }printf("%d\n",ans);
    }
    return 0;
}